package main

import "sort"

func findLongestChain(pairs [][]int) int {
	if len(pairs) <= 1 {
		return len(pairs)
	}
	sort.Slice(pairs, func(i, j int) bool {
		return pairs[i][0] < pairs[j][0]
	})
	dp := make([]int, len(pairs))
	result := 0
	for i, pair := range pairs {
		max := 1
		for j := 0; j < i; j++ {
			prev := pairs[j]
			if prev[1] < pair[0] {
				if dp[j]+1 > max {
					max = dp[j] + 1
				}
			}
		}
		dp[i] = max
		if dp[i] > result {
			result = dp[i]
		}
	}
	return result
}

func main() {
	println(findLongestChain([][]int{
		{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6},
	}))
	println(findLongestChain([][]int{
		{1, 2}, {7, 8}, {4, 5},
	}))
}
